#include"cds_avl.h"
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
//去掉终端行模式,关回显
#define char_input() do{\
    system("stty raw");\
    system("stty -echo");\
}while(0)

//恢复终端行模式,开回显
#define line_input() do{\
    system("stty cooked");\
    system("stty echo");\
}while(0)

//用户数据结构
typedef struct data{
    avl_node_t entry; //avl树节点
    unsigned long data;//数据域
} data_t;

//用户定义的生成key的函数,要使用avl树，用户必须为每种数据类型定义一个这样的函数传入树结构
unsigned long create_key(avl_node_t * node ){
    return avl_entry(node,data_t, entry)->data;
}

void destroy(avl_node_t * node ){
    
    data_t * data = avl_entry(node,data_t,entry);
    printf("free the %lu address: %p\n",data->data, data);
    free(data);
}

void travel(avl_node_t * node ){
    data_t * data = avl_entry(node,data_t,entry);
    printf("%lu ",data->data); 
}

void insert_random_datas(avl_tree_t * tree, unsigned long n){
    time_t t;
    time(&t);
    srand(t);
    for(int i=0;i<n;i++){
        unsigned long value = rand()%1000000;
        data_t * data = malloc(sizeof(data_t));
        data->data = 100+value;
        avl_node_t * ret = avl_insert(tree, &data->entry);
        if(ret){
            i--;
        }
    }
}

int main(void){
    
    avl_tree_t *tree = malloc(sizeof(avl_tree_t));
    //初始化avl树
    AVL_TREE_INIT(tree,create_key); 
    /*
     *  avl树示例:
     *
     *      插入顺序: 73,89,26,86,41,88,90,91,99,38,87,77,66,55
     *      最终的树形态如下图:
     *                               88
     *                              /  \
     *                             /    \
     *                            /      \
     *                           /        \
     *                          73        90
     *                         / \        / \
     *                        /   \      /   \
     *                       /     \    /     \
     *                      38      86 89     91
     *                     /  \     / \         \
     *                    /    \   /   \         \
     *                   26    55 77   87        99
     *                         /\
     *                        /  \
     *                       41  66
     */
    unsigned long arr[] = {73,89,26,86,41,88,90,91,99,38,87,77,66,55};
    
    printf("数组长度:%d\n",sizeof(arr)/sizeof(unsigned long)); 
    //依次插入数组中的数到avl树中
    for(int i=0;i<sizeof(arr)/sizeof(unsigned long); i++){
        data_t * dptr = malloc(sizeof(data_t));
        dptr->data = arr[i];
        avl_insert(tree,&dptr->entry); 
    }
    
    //顺序遍历avl树:
    avl_node_t * pos;
    avl_for_each(pos, tree){
        data_t * pdtr = avl_entry(pos,data_t, entry);
        printf("pdtr->data=%lu\n",pdtr->data);
    }
    printf("一共有%d个元素\n",tree->size);
   
    int loop = 1;
    while(loop){
        unsigned long key;
        printf("[t]: level travel; [r]: insert more random datas; [s]: search; \n[i]: insert; [d]: delete; [c]: clear; [q]: quit; [m]: middle order travel; \n请输入:\n");
        char_input();
         
        char ch;
        do{
            ch = getchar();
        }while(ch==13 || ch==10);
     
        line_input();
        switch( ch ){
            
            case 's': //搜索
                printf("输入key:\n");
                scanf("%lu",&key);
                avl_node_t * n1 = avl_search(tree, key);

                break;
            case 'i': //插入
                printf("输入要插入到数:\n");
                scanf("%lu",&key);
                data_t * pd = malloc(sizeof(data_t));
                pd->data = key;
                avl_insert(tree,&pd->entry); 
                break;
            case 'm': // middle order travel
                avl_travel_middle(tree,travel); 
                putchar('\n');
                printf("一共有%d个元素\n",tree->size);
                break;
            case 'r': //插入多个随机数
                printf("请输入要插入的数量:\n");
                scanf("%lu",&key);
                insert_random_datas(tree, key);                 
                break;
                /*
            case 'e':
                {
                    unsigned long k1;
                    unsigned long k2;
                    printf("输入两个节点的key:\n");
                    scanf("%lu%lu",&k1,&k2);
                    avl_node_t * n1 = avl_search(tree, k1);
                    avl_node_t * n2 = avl_search(tree, k2);
                    avl_exchange_two_nodes(tree, n1, n2 );
                }
                break;
                */
            case 'd': //删除
                {
                    printf("请输入要删除的key:\n");
                    scanf("%lu",&key);
                    avl_node_t * dnode = avl_search(tree,key);
                    avl_del(tree, dnode);
                }
                break;
            case 'c': //清空avl树
                avl_clear(tree, destroy);
                break;
            case 't': //层次遍历avl树
                avl_travel_level(tree, travel);
                putchar('\n');
                printf("一共有%d个元素\n",tree->size);
                break;
            case 'q': //退出程序
                loop = 0;
                break;
        }
    }

    return 0;
}
